#define _CRT_SECURE_NO_WARNINGS 1


#include "permutation.h"

//void sortSentenceby(char* s, char* senstr, char* wordstr, int len, int countword)
//{
//	int subofs = 0;
//	int subofsstr = 0;
//	int subofwstr = 0;
//	int numofchar = len - countword;
//	while (subofwstr < countword * 2)
//	{
//		int serialnum = (int)wordstr[subofwstr] - 48;
//		int cyctime = (int)wordstr[subofwstr + 1] - 48;
//		while (cyctime--)
//		{
//			int begin = numofchar - cyctime;
//		}
//	}
//}

void sortSentenceby(char* s, char* senstr, int* psubofsstr, int slow, int fast)
{
	int subofsstr = *psubofsstr;
	while (slow < fast)
	{
		senstr[subofsstr++] = s[slow++];
	}
	senstr[subofsstr++] = ' ';
	*psubofsstr = subofsstr;
}

char* sortSentence(char* s)
{
	int len = strlen(s);
	char countword = '0';
	int subofsstr = 0;
	int fast = 1;
	int slow = 0;
	int numofword = 0;
	char* senstr = (char*)calloc(200, sizeof(char));
	// char senstr[200] = {0};
	if (senstr == NULL)
	{
		exit(-1);
	}
	while (fast < len)
	{
		int ascval = (int)s[fast++];
		if (49 <= ascval && ascval <= 57)
			countword++;
	}
	fast = 1;
	if (len == 2)
	{
		senstr[0] = s[0];
		return senstr;
	}

	for (char subofword = '1'; subofword <= countword; subofword++)
	{
		fast = 1;
		slow = 0;
		while (fast < len)
		{
			if (subofword == s[fast])
			{
				sortSentenceby(s, senstr, &subofsstr, slow, fast);
				if (subofword == countword)
				{
					numofword = (int)countword - 48;
					senstr[len - numofword] = '\0';
					break;
				}
				fast += 2;
			}
			if (fast < len)
			{
				int ascval = (int)s[fast];
				if (49 <= ascval && ascval <= 57)
					slow = fast + 2;
				fast++;
			}
		}
	}
	int numofchar = len - numofword + 1;
	while (numofchar--)
	{
		s[numofchar] = senstr[numofchar];
	}
	return s;
}

void shellSort(int* arr, int suboffirst, int suboflast)
{
	int gap = suboflast - suboffirst + 1;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = suboffirst; i < suboflast - gap + 1; i++)
		{
			int end = i;
			int val = arr[end + gap];
			while (end >= suboffirst)
			{
				if (val < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = val;
		}
	}
}

int findLHS(int* nums, int numsSize)
{
	shellSort(nums, 0, numsSize - 1);
	int slow = 0;
	int fast = 1;
	int retlen = 0;
	if (nums[0] == nums[numsSize - 1])
	{
		return 0;
	}
	while (fast < numsSize)
	{
		fast = slow + 1;
		while (fast < numsSize)
		{
			if (nums[fast] - nums[slow] > 1)
			{
				if (fast - slow > retlen && (nums[fast - 1] != nums[slow]))
				{
					retlen = fast - slow;
				}
				break;
			}
			else
			{
				fast++;
			}
		}
		if (fast < numsSize)
		{
			slow++;
		}
		else
		{
			if (fast - slow > retlen && (nums[fast - 1] != nums[slow]))
			{
				retlen = fast - slow;
			}
		}
	}
	return retlen;
}